package uf;

import java.util.Scanner;

/**
 * 并查集结构
 */
public class UF {
    private int[] elementAndGroup;
    //    分组个数
    private int count;

    public UF(int N) {
        // 初始状态，每个元素一组
        this.count = N;
        // 初始化数组
        elementAndGroup = new int[N];
        // 把eleAndGroup数组的索引看做是每个结点存储的元素
        for (int i = 0; i < N; i++) {
            elementAndGroup[i] = i;
        }
    }


    public int count() {
        return count;
    }

    // 获取分组标识符
    public int find(int p) {
        return elementAndGroup[p];
    }

    // 判断并查集中元素p和元素q是否在同一分组中
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }


    // 把p元素所在分组和q元素所在分组合并
    public void union(int p, int q) {
        // 如果已经是同一组，则不需要合并
        if (connected(p, q)) {
            return;
        }

        int pGroup = find(p);
        int qGroup = find(q);
        // 吧 p合并为q
        for (int i = 0; i < elementAndGroup.length; i++) {
            if (elementAndGroup[i] == pGroup) {
                elementAndGroup[i] = qGroup;
            }
        }
        count--;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请录入并查集中元素的个数:");
        int N = sc.nextInt();
        UF uf = new UF(N);
        while (true) {
            System.out.println("请录入您要合并的第一个点:");
            int p = sc.nextInt();
            System.out.println("请录入您要合并的第二个点:");
            int q = sc.nextInt();
//判断p和q是否在同一个组
            if (uf.connected(p, q)) {
                System.out.println("结点：" + p + "结点" + q + "已经在同一个组");
                continue;
            }
            uf.union(p, q);
            System.out.println("总共还有" + uf.count() + "个分组");
        }
    }
}
